/* 分而治之(分治)相关代码记录 */
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int bfs(const std::vector<int> &nums, int target, int left, int right)
{
    /*  此处不能写 >=，因为left等于right的时候，相当于子区间有1个数，这个时候还需要继续比较 */
    if (left > right) {
        return -1;
    }

    /* 找出中点 */
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] > target) {
        /* 在左半区间寻找target */
        return bfs(nums, target, left, mid - 1);
    } else {
        /* 在右半区间寻找target */
        return bfs(nums, target, mid + 1, right);
    }
}

int binary_search(const std::vector<int> &nums, int target)
{
    int index = bfs(nums, target, 0, nums.size() - 1);
    return index;
}

/* 求解汉诺塔问题 */
/* 时间复杂度为 O(2^N)，空间复杂度为O(N) */
void solve_hanota_bfd(int n, std::vector<int> &A, std::vector<int> &B, std::vector<int> &C)
{
    auto move_pan = [=](std::vector<int> &src, std::vector<int> &target) -> void {
        std::cout << "move " << src.back() << " to pan: ";
        std::for_each(target.cbegin(), target.cend(), [=](int num) -> void { std::cout << num << " "; });
        std::cout << std::endl;
        target.push_back(src.back());
        src.pop_back();
    };

    /* 当A柱上只有1个盘的时候，就可以直接移动到C柱了 */
    if (n == 1) {
        move_pan(A, C);
        return;
    }

    /* 以C柱为缓冲柱，将A柱上的前n-1个盘移动到B柱上 */
    solve_hanota_bfd(n - 1, A, C, B);
    /* 将A柱剩下的一个盘，移动到C柱上 */
    move_pan(A, C);
    /* 将所有B柱上的盘子，通过A为缓冲柱，全部移动到C柱上 */
    solve_hanota_bfd(n - 1, B, A, C);
}

void solve_hanota(std::vector<int> &A, std::vector<int> &B, std::vector<int> &C) { solve_hanota_bfd(A.size(), A, B, C); }

int main()
{
#if 0
    /* 测试分治的二分搜索算法 */
    std::vector<int> nums = {6, 8, 2, 1, 10, 32, 88, 43, 232};
    std::sort(nums.begin(), nums.end());

    int index = binary_search(nums, 8);

    /* 遍历这个vector */
    std::for_each(nums.begin(), nums.end(), [=](int num) { std::cout << num << " "; });
    std::cout << "\n数字43的下标为: " << index << std::endl;
#endif
    std::vector<int> A = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    std::vector<int> A_back = A;
    std::vector<int> B;
    std::vector<int> C;

    solve_hanota(A, B, C);

    std::for_each(A_back.cbegin(), A_back.cend(), [=](int num) {
        if (num == A_back[0]) {
            std::cout << "要移动的盘子为: ";
        }
        std::cout << num << " ";
    });
    std::cout << "\n";

    std::for_each(C.cbegin(), C.cend(), [=](int num) {
        if (num == C[0]) {
            std::cout << "移动之后的盘子为: ";
        }
        std::cout << num << " ";
    });
    return 0;
}